//给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
//
//
//
// 示例 1：
//
// 输入：S = "ab#c", T = "ad#c"
//输出：true
//解释：S 和 T 都会变成 “ac”。
//
//
// 示例 2：
//
// 输入：S = "ab##", T = "c#d#"
//输出：true
//解释：S 和 T 都会变成 “”。
//
//
// 示例 3：
//
// 输入：S = "a##c", T = "#a#c"
//输出：true
//解释：S 和 T 都会变成 “c”。
//
//
// 示例 4：
//
// 输入：S = "a#c", T = "b"
//输出：false
//解释：S 会变成 “c”，但 T 仍然是 “b”。
//
//
//
// 提示：
//
//
// 1 <= S.length <= 200
// 1 <= T.length <= 200
// S 和 T 只含有小写字母以及字符 '#'。
//
//
//
// Related Topics 栈 双指针


package leetcode.editor.cn;

import java.util.Stack;

public class P844BackspaceStringCompare{
  public static void main(String[] args) {
       Solution solution = new P844BackspaceStringCompare().new Solution();
       //TO TEST
  }
  //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean backspaceCompare(String S, String T) {
        String s = toResultString(S);
        String t = toResultString(T);
        return s.equals(t);
    }

    public String toResultString(String src){
        char[] chars = src.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (char c : chars){
            if(c == '#' ){
                if(!stack.isEmpty()){
                    stack.pop();
                }
            }else {
                stack.push(c);
            }
        }
        if (stack.isEmpty()){
            return "";
        }

        char[] resultCars = new char[stack.size()];
        for (int i = resultCars.length-1; i >= 0; i--) {
            resultCars[i] = stack.pop();
        }
        return new String(resultCars);
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
